﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.simple
{
    public class DataStructure
    {
        #region 217. 存在重复元素
        /// <summary>
        /// 给定一个整数数组，判断是否存在重复元素。
        /// 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
        /// 输入: [1,2,3,1] 输出: true
        /// 输入: [1,2,3,4] 输出: false
        /// 输入: [1,1,1,3,3,4,3,2,4,2]  输出: true
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public bool ContainsDuplicate(int[] nums)
        {
            Dictionary<int, int> dic = new Dictionary<int, int>();

            for (int i = 0; i < nums.Length; i++)
            {
                var key = nums[i];
                if (dic.ContainsKey(key))
                {
                    return true;
                }
                else
                {
                    dic.Add(key, 0);
                }
            }

            return false;
        }
        #endregion

        #region *53. 最大子数组和 动态规划(未实现)
        /// <summary>
        /// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        /// 子数组 是数组中的一个连续部分。
        /// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
        /// 输入：nums = [1]   输出：1
        /// 输入：nums = [5,4,-1,7,8]  输出：23
        /// 
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MaxSubArray(int[] nums)
        {
            int pre = 0, maxAns = nums[0];
            foreach (int x in nums)
            {
                pre = Math.Max(pre + x, x);
                maxAns = Math.Max(maxAns, pre);
            }
            return maxAns;
        }
        #endregion

        #region 1. 两数之和
        /// <summary>
        /// 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        /// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        /// 你可以按任意顺序返回答案。
        /// 输入：nums = [2,7,11,15], target = 9   输出：[0,1]    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
        /// 输入：nums = [3,2,4], target = 6   输出：[1,2]
        /// 输入：nums = [3,3], target = 6 输出：[0,1]
        /// 
        /// 出现异常：[0,4,3,0]
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int[] TwoSum(int[] nums, int target)
        {
            Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
            for (int i = 0; i < nums.Length; i++)
            {
                var num = nums[i];
                if (dic.ContainsKey(num))
                {
                    dic[num].Add(i);
                }
                else
                {
                    dic.Add(num, new List<int>() { i });
                }
            }

            for (int i = 0; i < nums.Length; i++)
            {
                var num = nums[i];
                var find = target - num;
                if (dic.ContainsKey(find))
                {
                    List<int> findIndexs = dic[find];

                    for (int j = 0; j < findIndexs.Count; j++)
                    {
                        if (findIndexs[j] != i)
                        {
                            return new int[] { i, findIndexs[j] };
                        }
                    }
                }
            }
            return default(int[]);
        }
        #endregion

        #region 88. 合并两个有序数组
        /// <summary>
        /// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
        /// 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
        /// 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
        /// 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
        /// 示例 1：
        /// 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
        /// 输出：[1,2,2,3,5,6]
        /// 解释：需要合并 [1,2,3] 和 [2,5,6] 。
        /// 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
        /// 示例 2：
        /// 输入：nums1 = [1], m = 1, nums2 = [], n = 0
        /// 输出：[1]
        /// 解释：需要合并 [1] 和 [] 。
        /// 合并结果是 [1] 。
        /// 示例 3：
        /// 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
        /// 输出：[1]
        /// 解释：需要合并的数组是 [] 和 [1] 。
        /// 合并结果是 [1] 。
        /// 注意，因为 m = 0 ，所以 nums1 中没有元素。
        /// nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
        /// 
        /// 
        /// 
        /// 异常：
        /// [0]
        /// 0
        /// [1]
        /// 1
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="m"></param>
        /// <param name="nums2"></param>
        /// <param name="n"></param>
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            if (n == 0)
            {
                for (int i = 0; i < n; i++)
                {
                    nums1[i] = nums2[i];
                }
            }
            else
            {
                //合并2个数组
                for (int i = 0; i < n; i++)
                {
                    var num2 = nums2[i];
                    //放到num1位置 如果是 m
                    for (int j = m + i - 1; j >= 0; j--)
                    {
                        //比较位 num1 num2比较  num1 比较大 对调
                        if (nums1[j] > num2)
                        {
                            nums1[j + 1] = nums1[j];
                            nums1[j] = num2;
                        }
                        else
                        {
                            //nums1[j]<=num2 直接填入
                            nums1[j + 1] = num2;
                            break;
                        }
                    }
                }
            }
        }
        #endregion

        #region 350. 两个数组的交集 II
        /// <summary>
        /// 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
        /// 示例 1：
        /// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
        /// 输出：[2,2]
        /// 示例 2:
        /// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
        /// 输出：[4,9]
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="nums2"></param>
        /// <returns></returns>
        public int[] Intersect(int[] nums1, int[] nums2)
        {
            if (nums1.Length == 0 || nums2.Length == 0)
            {
                return new int[] { };
            }

            List<int> result = new List<int>();

            Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();

            for (int i = 0; i < nums1.Length; i++)
            {
                if (dic.ContainsKey(nums1[i]))
                {
                    dic[nums1[i]].Add(i);

                }
                else
                {
                    dic.Add(nums1[i], new List<int>() { i });
                }
            }

            for (int j = 0; j < nums2.Length; j++)
            {
                var num2 = nums2[j];
                if (dic.ContainsKey(num2))
                {
                    result.Add(num2);
                    if (dic[num2].Count == 1)
                    {
                        dic.Remove(num2);
                    }
                    else
                    {
                        dic[num2].RemoveAt(0);
                    }
                }
            }

            return result.ToArray();
        }
        #endregion

        #region *121. 买卖股票的最佳时机 动态规划(需重新做)
        /// <summary>
        /// 121. 买卖股票的最佳时机
        /// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        /// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
        /// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
        /// 
        /// 示例 1：
        /// 输入：[7,1,5,3,6,4]
        /// 输出：5
        /// 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
        /// 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
        /// 
        /// 示例 2：
        /// 输入：prices = [7,6,4,3,1]
        /// 输出：0
        /// 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
        /// 
        /// 思考：
        /// 1.最小值 和 最大值 的差值 
        /// 2.最小值的索引和最大值的索引之后
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            if (prices.Length <= 1) return 0;

            var minPrice = int.MaxValue;    //最低价格
            var maxProfit = 0; //最高收益

            for (int i = 0; i < prices.Length; i++)
            {
                if (minPrice > prices[i])   //寻找最低价格
                {
                    minPrice = prices[i];
                }
                else if (prices[i] - minPrice > maxProfit) //当前价格 - 最低价格 > 最大利润值  则更新最大利润值
                {
                    maxProfit = prices[i] - minPrice;
                }
            }
            return maxProfit;
        }

        #endregion

        #region 566. 重塑矩阵
        /// <summary>
        /// 在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
        /// 给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
        /// 重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
        /// 如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
        /// 
        /// 输入：mat = [[1,2],[3,4]], r = 1, c = 4
        /// 输出：[[1,2,3,4]]
        /// 
        /// 输入：mat = [[1,2],[3,4]], r = 2, c = 4
        /// 输出：[[1,2],[3,4]]
        /// </summary>
        /// <param name="mat"></param>
        /// <param name="r"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        public int[][] MatrixReshape(int[][] mat, int r, int c)
        {
            //如果集合(个数)不满足
            if (mat.Length * mat[0].Length != r * c)
            {
                return mat;
            }

            int[][] result = new int[r][];

            for (int i = 0; i < r * c; i++)
            {
                if (i % c == 0)
                {
                    result[i / c] = new int[c];
                }
                result[i / c][i % c] = mat[i / mat[0].Length][i % mat[0].Length];
            }
            return result;
        }
        #endregion

        #region 118. 杨辉三角
        /// <summary>
        /// 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
        /// 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
        /// 
        /// 输入: numRows = 5
        /// 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
        /// 输入: numRows = 1
        /// 输出: [[1]]
        /// </summary>
        /// <param name="numRows"></param>
        /// <returns></returns>
        public IList<IList<int>> Generate(int numRows)
        {
            var result = new List<IList<int>>();
            if (numRows == 0) return result;
            for (int i = 0; i < numRows; i++)
            {
                result.Add(new List<int>());
                for (int j = 0; j <= i; j++)
                {
                    if (j == 0 || j == i)
                    {
                        result[i].Add(1);
                    }
                    else
                    {
                        result[i].Add(result[i - 1][j - 1] + result[i - 1][j]);
                    }
                }
            }
            return result;
        }
        #endregion

        #region 36. 有效的数独   中等
        /// <summary>
        /// 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
        /// 1.数字 1-9 在每一行只能出现一次。
        /// 2.数字 1-9 在每一列只能出现一次。
        /// 3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
        /// </summary>
        /// <param name="board"></param>
        /// <returns></returns>
        public bool IsValidSudoku(char[][] board)
        {
            List<Dictionary<char, int>> rows = new List<Dictionary<char, int>>();
            List<Dictionary<char, int>> columns = new List<Dictionary<char, int>>();
            List<Dictionary<char, int>> squares = new List<Dictionary<char, int>>();

            for (int i = 0; i < 9; i++)
            {
                rows.Add(new Dictionary<char, int>());
                columns.Add(new Dictionary<char, int>());
                squares.Add(new Dictionary<char, int>());
            }

            for (int i = 0; i < 9 * 9; i++)
            {
                var x = i / 9;
                var y = i % 9;
                var c = board[x][y];

                if (c == '.') continue;

                if (rows[x].ContainsKey(c)) return false;
                rows[x].Add(c, 1);
                if (columns[y].ContainsKey(c)) return false;
                columns[y].Add(c, 1);
                var squareIndex = x / 3 * 3 + y / 3;
                if (squares[squareIndex].ContainsKey(c)) return false;
                squares[squareIndex].Add(c, 1);
            }

            return true;
        }
        #endregion

        #region 73. 矩阵置零    中等
        /// <summary>
        /// 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
        /// </summary>
        /// <param name="matrix"></param>
        public void SetZeroes(int[][] matrix)
        {
            //查找零说在位置
            List<int[]> zeroPostion = new List<int[]>();
            for (int i = 0; i < matrix.Length; i++)
            {
                for (int j = 0; j < matrix[i].Length; j++)
                {
                    if (matrix[i][j] == 0)
                    {
                        zeroPostion.Add(new int[] { i, j });
                    }
                }
            }
            //将0所在行和列进行替换
            if (zeroPostion.Count == 0) return;

            for (int i = 0; i < zeroPostion.Count; i++)
            {
                var x = zeroPostion[i][0];
                var y = zeroPostion[i][1];

                for (int j = 0; j < matrix.Length; j++)
                {
                    matrix[j][y] = 0;
                }

                for (int z = 0; z < matrix[x].Length; z++)
                {
                    matrix[x][z] = 0;
                }
            }
        }

        #endregion

        #region 387. 字符串中的第一个唯一字符
        /// <summary>
        /// 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int FirstUniqChar(string s)
        {
            Dictionary<char, int> uniqCharkeys = new Dictionary<char, int>();
            Dictionary<char, int> iqkeys = new Dictionary<char, int>();
            char[] cArray = s.ToCharArray();
            for (int i = 0; i < cArray.Length; i++)
            {
                char item = cArray[i];
                if (iqkeys.ContainsKey(item))
                {
                    continue;
                }

                if (uniqCharkeys.ContainsKey(item))
                {
                    uniqCharkeys.Remove(item);
                    iqkeys.Add(item, i);
                }
                else
                {
                    uniqCharkeys.Add(item, i);
                }
            }

            if (uniqCharkeys.Count > 0)
            {
                return uniqCharkeys.Values.Min();
            }
            return -1;
        }
        #endregion

        #region 383. 赎金信
        /// <summary>
        /// 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
        /// 如果可以，返回 true ；否则返回 false 。
        /// magazine 中的每个字符只能在 ransomNote 中使用一次。
        /// </summary>
        /// <param name="ransomNote"></param>
        /// <param name="magazine"></param>
        /// <returns></returns>
        public bool CanConstruct(string ransomNote, string magazine)
        {

            Dictionary<char, int> ransomNoteCharkeys = new Dictionary<char, int>();
            Dictionary<char, int> magazinekeys = new Dictionary<char, int>();
            foreach (var item in ransomNote)
            {
                if (ransomNoteCharkeys.ContainsKey(item))
                {
                    ransomNoteCharkeys[item] = ransomNoteCharkeys[item] + 1;
                }
                else
                {
                    ransomNoteCharkeys.Add(item, 1);
                }

            }

            foreach (var item in magazine)
            {
                if (magazinekeys.ContainsKey(item))
                {
                    magazinekeys[item] = magazinekeys[item] + 1;
                }
                else
                {
                    magazinekeys.Add(item, 1);
                }
            }

            if (ransomNoteCharkeys.Count > magazinekeys.Count) return false;

            foreach (var item in ransomNoteCharkeys)
            {
                if (!magazinekeys.ContainsKey(item.Key) || magazinekeys[item.Key] < item.Value)
                {
                    return false;
                }
            }

            return true;
        }
        #endregion

        #region 242. 有效的字母异位词
        /// <summary>
        /// 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
        /// 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public bool IsAnagram(string s, string t)
        {
            if (s.Length != t.Length)
            {
                return false;
            }

            Dictionary<char, int> sCharkeys = new Dictionary<char, int>();
            Dictionary<char, int> tCharkeys = new Dictionary<char, int>();

            foreach (var item in s)
            {
                if (sCharkeys.ContainsKey(item))
                {
                    sCharkeys[item] = sCharkeys[item] + 1;
                }
                else
                {
                    sCharkeys.Add(item, 1);
                }

            }

            foreach (var item in t)
            {
                if (tCharkeys.ContainsKey(item))
                {
                    tCharkeys[item] = tCharkeys[item] + 1;
                }
                else
                {
                    tCharkeys.Add(item, 1);
                }
            }

            foreach (var item in sCharkeys)
            {
                if (!tCharkeys.ContainsKey(item.Key) || tCharkeys[item.Key] != item.Value)
                {
                    return false;
                }
            }

            return true;
        }
        #endregion

        #region *141. 环形链表 需回顾
        /// <summary>
        /// 给你一个链表的头节点 head ，判断链表中是否有环。
        /// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
        /// 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
        /// 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
        /// 
        /// 如果链表中存在环，则返回 true 。 否则，返回 false 。
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public bool HasCycle(ListNode head)
        {
            HashSet<ListNode> listNodes = new HashSet<ListNode>();
            while (head != null)
            {
                if (listNodes.Contains(head))
                {
                    return true;
                }
                listNodes.Add(head);

                head = head.next;

            }
            return false;
        }
        #endregion

        #region *21. 合并两个有序链表 递归思想
        /// <summary>
        /// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
        /// </summary>
        /// <param name="list1"></param>
        /// <param name="list2"></param>
        /// <returns></returns>
        public ListNode MergeTwoLists(ListNode list1, ListNode list2)
        {
            if (list1 == null)
            {
                return list2;
            }
            else if (list2 == null)
            {
                return list1;
            }
            else if (list1.val < list2.val)
            {
                list1.next = MergeTwoLists(list1.next, list2);
                return list1;
            }
            else
            {
                list2.next = MergeTwoLists(list1, list2.next);
                return list2;
            }
        }
        #endregion

        #region *203. 移除链表元素
        /// <summary>
        /// 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
        /// </summary>
        /// <param name="head"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public ListNode RemoveElements(ListNode head, int val)
        {
            if (head == null) return null;
            head.next = RemoveElements(head.next, val);
            return head.val == val ? head.next : head;
        }
        #endregion

        #region *206. 反转链表
        /// <summary>
        /// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode ReverseList(ListNode head)
        {
            ListNode prev = null;
            ListNode curr = head;
            while (curr != null)
            {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }
        #endregion

        #region 83. 删除排序链表中的重复元素
        /// <summary>
        /// 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
        /// 返回同样按升序排列的结果链表。
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public ListNode DeleteDuplicates(ListNode head)
        {
            if (head == null) return head;

            var currValue = head.val;
            var pre = head;
            var node = head.next;
            while (node != null)
            {
                if (currValue == node.val)
                {
                    pre.next = node.next;
                    node = pre.next;
                }
                else
                {
                    currValue = node.val;
                    pre = node;
                    node = node.next;
                }
            }

            return head;
        }
        #endregion

        #region 20. 有效的括号
        /// <summary>
        /// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        /// 有效字符串需满足：
        /// 1.左括号必须用相同类型的右括号闭合。
        /// 2.左括号必须以正确的顺序闭合。
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public bool IsValid(string s)
        {
            List<char> list = new List<char>();
            var charArray = s.ToCharArray();
            for (int i = 0; i < charArray.Length; i++)
            {
                var count = list.Count;
                var item = charArray[i];
                switch (item)
                {
                    case '(':
                        list.Add(item);
                        break;
                    case ')':
                        if (count == 0) return false;
                        if (!list[count - 1].Equals('(')) return false;
                        list.RemoveAt(count - 1);
                        break;
                    case '{':
                        list.Add(item);
                        break;
                    case '}':
                        if (count == 0) return false;
                        if (!list[count - 1].Equals('{')) return false;
                        list.RemoveAt(count - 1);
                        break;
                    case '[':
                        list.Add(item);
                        break;
                    case ']':
                        if (count == 0) return false;
                        if (!list[count - 1].Equals('[')) return false;
                        list.RemoveAt(count - 1);
                        break;
                }
            }
            if (list.Count > 0) return false;
            return true;
        }


        public bool IsValid01(string s)
        {
            Stack<char> stack = new Stack<char>();
            Dictionary<char, char> pairs = new Dictionary<char, char>()
            {
                {')', '('},
                {'}', '{'},
                {']', '['},
            };
            foreach (var item in s.ToCharArray())
            {
                if (pairs.ContainsKey(item))
                {
                    if (stack.Count == 0 || !stack.Peek().Equals(pairs[item]))
                    {
                        return false;
                    }
                    stack.Pop();
                }
                else
                {
                    stack.Push(item);
                }
            }
            return stack.Count == 0;

        }
        #endregion

        #region 144. 二叉树的前序遍历
        /// <summary>
        /// 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> PreorderTraversal(TreeNode root)
        {

            List<int> result = new List<int>();
            if (root == null)
            {
                return result;
            }
            result.Add(root.val);
            result.AddRange(PreorderTraversal(root.left));
            result.AddRange(PreorderTraversal(root.right));
            return result;
        }
        #endregion

        #region 94. 二叉树的中序遍历
        /// <summary>
        /// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int>();
            if (root == null)
            {
                return result;
            }
            if (root.left != null)
            {
                result.AddRange(InorderTraversal(root.left));
            }
            result.Add(root.val);
            result.AddRange(InorderTraversal(root.right));
            return result;
        }
        #endregion

        #region 145. 二叉树的后序遍历
        /// <summary>
        /// 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
        /// [1,null,2,3]
        /// [3,1,2]
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<int> PostorderTraversal(TreeNode root)
        {
            List<int> result = new List<int>();
            if (root == null)
            {
                return result;
            }
            postorder(root, result);
            return result;
        }

        public void postorder(TreeNode root, List<int> result)
        {
            if (root == null)
            {
                return;
            }
            result.AddRange(PostorderTraversal(root.left));
            result.AddRange(PostorderTraversal(root.right));
            result.Add(root.val);
        }
        #endregion

        #region 102. 二叉树的层序遍历
        /// <summary>
        /// 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
        /// 
        /// 思考  所在那一层
        /// 思考  对应层相加
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public IList<IList<int>> LevelOrder(TreeNode root)
        {
            if (root == null) return null;
            IList<IList<int>> result = new List<IList<int>>();
            LevelOrder(root, result, 0);
            return result;
        }

        public void LevelOrder(TreeNode root, IList<IList<int>> result, int level)
        {
            if (root == null) return;
            if (result.Count < level + 1)
            {
                result.Add(new List<int>());
            }
            result[level].Add(root.val);
            LevelOrder(root.left, result, level + 1);
            LevelOrder(root.right, result, level + 1);
        }

        #endregion

        #region 104. 二叉树的最大深度
        /// <summary>
        /// 给定一个二叉树，找出其最大深度。
        /// 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
        /// 说明: 叶子节点是指没有子节点的节点。
        /// 
        /// 思考 找出最大层级
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public int MaxDepth(TreeNode root)
        {
            var level = MaxDepth(root, 0);
            return level;
        }


        public int MaxDepth(TreeNode root, int level)
        {
            if (root == null) return level;
            var leftlevel = MaxDepth(root.left, level + 1);
            var rihtlevel = MaxDepth(root.right, level + 1);
            return leftlevel > rihtlevel ? leftlevel : rihtlevel;
        }


        #endregion

        #region *101. 对称二叉树
        /// <summary>
        /// 给你一个二叉树的根节点 root ， 检查它是否轴对称。
        /// 
        /// 左节点 = 右节点
        /// 
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public bool IsSymmetric(TreeNode root)
        {
            return IsSymmetric(root.left, root.right);
        }

        /// <summary>
        /// 1.同时为空 return
        /// 2.值一样
        /// 3.最左节点 与最右节点 进行判断
        /// </summary>
        /// <param name="leftNode"></param>
        /// <param name="rightNode"></param>
        /// <returns></returns>
        public bool IsSymmetric(TreeNode leftNode, TreeNode rightNode)
        {
            if (leftNode == null && rightNode == null)
            {
                return true;
            }
            else if (leftNode == null || rightNode == null)
            {
                return false;
            }

            if (leftNode.val != rightNode.val)
            {
                return false;
            }
            return IsSymmetric(leftNode.left, rightNode.right) && IsSymmetric(leftNode.right, rightNode.left);
        }

        #endregion

        #region 226. 翻转二叉树
        /// <summary>
        /// 翻转一棵二叉树。
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public TreeNode InvertTree(TreeNode root)
        {

            if (root == null)
            {
                return null;
            }
            if (root.left == null && root.right == null)
            {
                return root;
            }
            else if (root.left == null)
            {
                root.left = InvertTree(root.right);
                root.right = null;
                return root;
            }
            else if (root.right == null)
            {
                root.right = InvertTree(root.left);
                root.left = null;
                return root;
            }
            else
            {
                var node = root.left;
                root.left = InvertTree(root.right);
                root.right = InvertTree(node);
                return root;
            }
        }
        #endregion

        #region 112. 路径总和
        /// <summary>
        /// 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
        /// 判断该树中是否存在 
        /// 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
        /// 如果存在，返回 true ；否则，返回 false 。
        /// 叶子节点 是指没有子节点的节点。
        /// 
        /// 
        /// 1.
        /// </summary>
        /// <param name="root"></param>
        /// <param name="targetSum"></param>
        /// <returns></returns>
        public bool HasPathSum(TreeNode root, int targetSum)
        {
            if (root == null) return false;
            return PathSum(root, 0, targetSum);
        }


        public bool PathSum(TreeNode root, int pathsum, int targetSum)
        {
            pathsum = pathsum + root.val;
            if (root.left == null && root.right == null)
            {
                return pathsum == targetSum;
            }
            else if (root.left == null)
            {
                return PathSum(root.right, pathsum, targetSum);
            }
            else if (root.right == null)
            {
                return PathSum(root.left, pathsum, targetSum);
            }
            else
            {
                return PathSum(root.left, pathsum, targetSum) || PathSum(root.right, pathsum, targetSum);
            }
        }
        #endregion

        #region 700. 二叉搜索树中的搜索
        /// <summary>
        /// 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
        /// </summary>
        /// <param name="root"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public TreeNode SearchBST(TreeNode root, int val)
        {
            if (root == null) return null;
            if (root.val == val) return root;
            var leftNodeSeachResult = SearchBST(root.left, val);
            if (leftNodeSeachResult != null)
            {
                return leftNodeSeachResult;
            }
            var rihtNodeSearchResult = SearchBST(root.right, val);
            if (rihtNodeSearchResult != null)
            {
                return rihtNodeSearchResult;
            }
            return null;
        }
        #endregion

        #region 701. 二叉搜索树中的插入操作
        /// <summary>
        /// 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
        /// 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
        /// 
        /// 首先回顾二叉搜索树的性质：对于任意节点 root 而言，左子树（如果存在）上所有节点的值均小于 root.val，右子树（如果存在）上所有节点的值均大于 root.val，且它们都是二叉搜索树。
        /// </summary>
        /// <param name="root"></param>
        /// <param name="val"></param>
        /// <returns></returns>
        public TreeNode InsertIntoBST(TreeNode root, int val)
        {
            if (root == null) return new TreeNode() { val = val };
            if (root.val > val)
            {
                //右边
                if (root.left == null)
                {
                    root.left = new TreeNode() { val = val };
                }
                else
                {
                    InsertIntoBST(root.left, val);
                }

            }
            else
            {
                if (root.right == null)
                {
                    root.right = new TreeNode() { val = val };
                }
                else
                {
                    InsertIntoBST(root.right, val);
                }

            }
            return root;
        }
        #endregion


        #region 136. 只出现一次的数字
        /// <summary>
        /// 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int SingleNumber(int[] nums)
        {
            var result = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                result ^= nums[i];
            }
            return result;
        }
        #endregion

        #region 169. 多数元素

        /// <summary>
        /// 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        /// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MajorityElement(int[] nums)
        {
            var result = 0;
            var count = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (count > 0)
                {
                    count += result == nums[i] ? 1 : -1;
                }
                else
                {
                    result = nums[i];
                    count = 1;
                }
            }

            return result;
        }

        #endregion




        #region 98. 验证二叉搜索树
        /// <summary>
        /// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
        /// 对于任意节点 root 而言，左子树（如果存在）上所有节点的值均小于 root.val，右子树（如果存在）上所有节点的值均大于 root.val，且它们都是二叉搜索树。
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public bool IsValidBST(TreeNode root)
        {
            return IsValidBST(root.left, null, root.val) && IsValidBST(root.right, root.val, null);
        }


        public bool IsValidBST(TreeNode root, int? min, int? max)
        {
            if (root == null) return true;
            if (min.HasValue && root.val <= min)
            {
                return false;
            }
            if (max.HasValue && root.val >= max)
            {
                return false;
            }

            return IsValidBST(root.left, min, root.val) && IsValidBST(root.right, root.val, max);
        }
        #endregion

        #region 653. 两数之和 IV - 输入 BST
        /// <summary>
        /// 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
        /// </summary>
        /// <param name="root"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public bool FindTarget(TreeNode root, int k)
        {
            return FindTarget(root, k, new Dictionary<int, int>());
        }


        public bool FindTarget(TreeNode root, int k, Dictionary<int, int> keys)
        {
            if (root == null) return false;
            var key = k - root.val;
            if (keys.ContainsKey(key))
            {
                return true;
            }
            else
            {
                if (!keys.ContainsKey(root.val))
                {
                    keys.Add(root.val, 1);
                }
            }
            return FindTarget(root.left, k, keys) || FindTarget(root.right, k, keys);
        }
        #endregion


        #region 235. 二叉搜索树的最近公共祖先
        /// <summary>
        /// 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
        /// 百度百科中最近公共祖先的定义为：
        /// “对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
        /// 
        /// </summary>
        /// <param name="root"></param>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
        {
            TreeNode ancestor = root;
            while (true)
            {
                if (p.val < ancestor.val && q.val < ancestor.val)
                {
                    ancestor = ancestor.left;
                }
                else if (p.val > ancestor.val && q.val > ancestor.val)
                {
                    ancestor = ancestor.right;
                }
                else
                {
                    break;
                }
            }
            return ancestor;
        }
        #endregion

        #region 15. 三数之和
        /// <summary>
        /// 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
        /// 注意：答案中不可以包含重复的三元组。
        /// [-1,0,1,2,-1,-4]
        /// [-4,-1,-1,0,1,2]
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> ThreeSum(int[] nums)
        {
            var result = new List<IList<int>>();
            if (nums.Length < 3) return result;
            Array.Sort(nums);
            if (nums[0] == nums[nums.Length - 1])
            {
                if (nums[0] == 0)
                {
                    result.Add(new List<int>() { 0, 0, 0 });
                }
                return result;
            }
            for (int l = 0; l < nums.Length - 2; l++)
            {
                if (l > 0 && nums[l] == nums[l - 1])
                {
                    continue;
                }
                for (int i = l + 1; i < nums.Length - 1; i++)
                {
                    if (i > l + 1 && nums[i] == nums[i - 1])
                    {
                        continue;
                    }
                    for (int r = i + 1; r < nums.Length; r++)
                    {
                        if (r > i + 1 && nums[r] == nums[r - 1])
                        {
                            continue;
                        }
                        if (nums[l] + nums[i] + nums[r] == 0)
                        {
                            result.Add(new List<int>() { nums[l], nums[i], nums[r] });
                        }
                    }
                }
            }
            return result;
        }
        /// <summary>
        /// [-1,0,1,2,-1,-4]
        /// [-4,-1,-1,0,1,2]
        /// [-4,-1,-1,0,1,2]
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> ThreeSum1(int[] nums)
        {
            var result = new List<IList<int>>();
            if (nums.Length < 3) return result;
            Array.Sort(nums);
            if (nums[0] == nums[nums.Length - 1])
            {
                if (nums[0] == 0)
                {
                    result.Add(new List<int>() { 0, 0, 0 });
                }
                return result;
            }
            var length = nums.Length;

            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < length; i++)
            {
                var key = nums[i];
                if (dic.ContainsKey(key))
                {
                    dic[key] = dic[key] + 1;
                }
                else
                {
                    dic.Add(key, 1);
                }
            }

            for (int i = 0; i < length; i++)
            {
                if (i > 0 && nums[i] == nums[i - 1])
                {
                    continue;
                }
                for (int j = i + 1; j < length; j++)
                {
                    var target = 0 - (nums[i] + nums[j]);
                    var count = 0;
                    if (target == nums[i])
                    {
                        count = count + 1;
                    }
                    if (target == nums[j])
                    {
                        count = count + 1;
                    }

                    if (nums[i] <= nums[j] && nums[i] <= target)
                    {
                        if (dic.ContainsKey(target) && dic[target] > count)
                        {
                            result.Add(new List<int>() { nums[i], nums[j], target });
                            continue;
                        }
                    }
                }
            }
            return result;
        }
        #endregion


        #region 56. 合并区间（*）
        /// <summary>
        /// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
        /// 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public int[][] Merge(int[][] intervals)
        {
            if (intervals.Length == 0)
            {
                return new int[0][];
            }
            Array.Sort(intervals, (interval1, interval2) => interval1[0] - interval2[0]);

            List<int[]> merged = new List<int[]>();

            for (int i = 0; i < intervals.Length; ++i)
            {
                int L = intervals[i][0], R = intervals[i][1];
                if (merged.Count == 0 || merged[merged.Count - 1][1] < L)
                {
                    merged.Add(new int[] { L, R });
                }
                else
                {
                    merged[merged.Count - 1][1] = Math.Max(merged[merged.Count - 1][1], R);
                }
            }
            return merged.ToArray();
        }
        #endregion


        #region 48. 旋转图像
        /// <summary>
        /// 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
        /// 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
        /// 
        /// 
        /// 思路 把行变成列
        /// 第一行 第一列 变成 最后一列 第一行
        /// 
        /// </summary>
        /// <param name="matrix"></param>
        public void Rotate(int[][] matrix)
        {
            int n = matrix.Length;
            for (int i = 0; i < n / 2; ++i)
            {
                for (int j = 0; j < (n + 1) / 2; ++j)
                {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n - j - 1][i];
                    matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                    matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                    matrix[j][n - i - 1] = temp;
                }
            }
        }
        #endregion
    }
}


